/**
 * 2017年6月12日
 */
package leetcode;

/**
 * @author Alex
 *
 */
class ListNode {
	      int val;
	      ListNode next;
	      ListNode(int x) { val = x; }
}
public class AddTwoNumber {
	public static void print(ListNode res){
		while(res!=null){
			System.out.print(res.val);
			System.out.print(",");
			res = res.next;
		}
	}
	public static void main(String args[]){
		ListNode l1 = new ListNode(1);
		ListNode l2 = new ListNode(9);
		l2.next = new ListNode(9);
		AddTwoNumber solution = new AddTwoNumber();
		print(solution.addTwoNumbers(l1, l2));
		
	}
	 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	        int carry = 0;
	        
	        ListNode res = new ListNode(0);
	        ListNode p1,p2,p3 = res;
	        for(p1 = l1,p2 = l2;p1!=null && p2!=null;p1 = p1.next,p2=p2.next){
	            
	            p3.next = new ListNode(0);
	            
	            int sum = p1.val + p2.val + carry;
	            carry = sum>=10?1:0;
	            p3.next.val = carry==1?sum-10:sum;
	            p3 = p3.next;
	            
	        }
	   
	        if(p1==null){
	           f(p1,p2,p3,carry);
	        }
	        if(p2==null){
	          f(p2,p1,p3,carry);
	        }
	    
	        return res.next;
	        
	    }
	    public ListNode f(ListNode empty,ListNode notEmpty,ListNode p3,int carry){
	          while(notEmpty!=null){
	                int res = notEmpty.val+carry;
	                p3.next = new ListNode(res>=10?res-10:res);  
	                carry = res>=10?1:0;
	                notEmpty = notEmpty.next;
	                p3 = p3.next;
	                
	            }
	            if(carry!=0){
	                p3.next = new ListNode(1);
	                p3 = p3.next;
	            }
	        return p3;
	    }
}
